Approximate range searching

The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show that if linear space is assumed, the problem cannot be solved in polylogarithmic time, except for the case of orthogonal ranges. In this paper we show that if one is willing to allow approximate ranges, then it is possible to do much better. In particular, given a bounded range Q of diameter w and >0, an approximate range query treats the range as a fuzzy object, meaning that points lying within distance w of the boundary of Q either may or may not be counted. We show that in any fixed dimension d, a set of n points in can be preprocessed in O(n+logn) time and O(n) space, such that approximate queries can be answered in O(logn(1/)^d) time. The only assumption we make about ranges is that the intersection of a range and a d-dimensional cube can be answered in constant time (depending on dimension). For convex ranges, we tighten this to O(logn+(1/)^d−1) time. We also present a lower bound for approximate range searching based on partition trees of Ω(logn+(1/)^d−1), which implies optimality for convex ranges (assuming fixed dimensions). Finally, we give empirical evidence showing that allowing small relative errors can significantly improve query execution times.     

Facilitated modelling in operational research

The traditional way of employing operational research in organisational interventions has been the expert mode. In this mode, the problem situation faced by the client is given to the operational research consultant, who then builds a model of the situation, solves the model to arrive at an optimal (or quasi-optimal) solution, and then provides a recommendation to the client based on the obtained solution. An alternative mode of engagement is to conduct the whole intervention together with the client: from structuring and defining the nature of the problem situation of interest, to supporting the evaluation of priorities and development of plans for subsequent implementation. In this latter mode, the operational researcher works throughout the intervention not only as an analyst, but also as a facilitator to the client. This paper discusses this latter mode of engagement with clients, with particular emphasis on the use of facilitated modelling as the intervention tool. Drawing on research scattered across a range of publications and domains, the review presented here provides a formal definition of facilitated modelling, together with a general framework that allows the conceptualisation of a wide variety of facilitated modelling approaches to organisational intervention. Design issues in facilitated modelling and their practical implication are discussed, and directions for future research identified.     

Fuzzy classifier identification using decision tree and multiobjective evolutionary algorithms

This paper presents a hybrid method for identification of Pareto-optimal fuzzy classifiers (FCs). In contrast to many existing methods, the initial population for multiobjective evolutionary algorithms (MOEAs) is neither created randomly nor a priori knowledge is required. Instead, it is created by the proposed two-step initialization method. First, a decision tree (DT) created by C4.5 algorithm is transformed into an FC. Therefore, relevant variables are selected and initial partition of input space is performed. Then, the rest of the population is created by randomly replacing some parameters of the initial FC, such that, the initial population is widely spread. That improves the convergence of MOEAs into the correct Pareto front. The initial population is optimized by NSGA-II algorithm and a set of Pareto-optimal FCs representing the trade-off between accuracy and interpretability is obtained. The method does not require any a priori knowledge of the number of fuzzy sets, distribution of fuzzy sets or the number of relevant variables. They are all determined by it. Performance of the obtained FCs is validated by six benchmark data sets from the literature. The obtained results are compared to a recently published paper [H. Ishibuchi, Y. Nojima, Analysis of interpretability-accuracy tradeoff of fuzzy systems by multiobjective fuzzy genetics-based machine learning, International Journal of Approximate Reasoning 44 (1) (2007) 4–31] and the benefits of our method are clearly shown.     

Proper generating trees and their internal path length

We find the generating function counting the total internal path length of any proper generating tree. This function is expressed in terms of the functions (d(t),h(t)) defining the associated proper Riordan array. This result is important in the theory of Riordan arrays and has several combinatorial interpretations.     

Development of a model-based netsourcing decision support system using a five-stage methodology

Managers increasingly face netsourcing decisions of whether and how to outsource selected software applications over the Internet. This paper illustrates the development of a netsourcing decision support system (DSS) that provides support for the first netsourcing decision of whether to netsource or not to do so. The development follows a five-stage methodology focusing on empirical modeling with internal validation during the development. It begins with identifying potential decision criteria from the literature followed by the collection of empirical data. Logistic regression is then used as a statistical method for selecting relevant decision criteria. Applying the logistic regression analysis to the dataset delivers competitive relevance and strategic vulnerability as relevant decision criteria. The development concludes with designing a core and a complementary DSS module. The paper critiques the developed DSS and its underlying development methodology. Recommendations for further research are offered.     

Improved algorithms for the multicut and multiflow problems in rooted trees

Costa et al. (Oper. Res. Lett. 31:21–27, 2003) presented a quadratic O(min (Kn,n ²)) greedy algorithm to solve the integer multicut and multiflow problems in a rooted tree. (n is the number of nodes of the tree, and K is the number of commodities). Their algorithm is a special case of the greedy type algorithm of Kolen (Location problems on trees and in the rectilinear plane. Ph.D. dissertation, 1982) to solve weighted covering and packing problems defined by general totally balanced (greedy) matrices. In this communication we improve the complexity bound in Costa et al. (Oper. Res. Lett. 31:21–27, 2003) and show that in the case of the integer multicut and multiflow problems in a rooted tree the greedy algorithm of Kolen can be implemented in subquadratic O(K+n+min (K,n)log n) time. The improvement is obtained by identifying additional properties of this model which lead to a subquadratic transformation to greedy form and using more sophisticated data structures.      

An efficient computational approach for railway booking problems

This paper deals with the determination of seat allocations for a rail booking system. It is assumed that demand for each trip in the network can be divided into two segments, namely a full fare segment and a discounted fare segment. A constrained nonlinear integer programming model is formulated to deal with this problem. The purpose of this paper is to develop an efficient heuristic approach to develop the booking limits for all ticket types in the railway network. The solutions obtained by the heuristic approach are compared with those found by the Lingo software and the DICOPT solver. Numerical results show that the proposed heuristic approach only require a small number of CPU time to obtain superior solutions.     

An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees

The problem of reconstructing the duplication tree of a set of tandemly repeated sequences which are supposed to have arisen by unequal recombination, was first introduced by Fitch (1977), and has recently received a lot of attention. In this paper, we place ourselves in a distance framework and deal with the restricted problem of reconstructing single copy duplication trees. We describe an exact and polynomial distance based algorithm for solving this problem, the parsimony version of which has previously been shown to be NP-hard (like most evolutionary tree reconstruction problems). This algorithm is based on the minimum evolution principle, and thus involves selecting the shortest tree as being the correct duplication tree. After presenting the underlying mathematical concepts behind the minimum evolution principle, and some of its benefits (such as statistical consistency), we provide a new recurrence formula to estimate the tree length using ordinary least-squares, given a matrix of pairwise distances between the copies. We then show how this formula naturally forms the dynamic programming framework on which our algorithm is based, and provide an implementation in O(n³) time and O(n²) space, where n is the number of copies.     

The anticipative concept in warehouse optimization using simulation in an uncertain environment

The modern business environment is highly unpredictable. An anticipation approach in a real case study is presented to cope with such instability and minimize the total inventory cost without stock-outs occurring and inventory capacity being exceeded. The anticipation concept is performed using simulation models supported by inventory control algorithms on a selected sample of representative items. The inventory control algorithms include Silver–Meal, Part period balancing, Least-unit cost, and Fuzzy inventory control algorithm based on fuzzy stock-outs, highest inventory level and total cost. Transportation cost is explicitly defined as a discrete function of shipment size. The algorithms are tested on historic data. Simulation results are presented and the risk of accepting them as reliable is discussed. The process of simulation model implementation is briefly discussed to further validate the model and train order managers to use the simulation model in their order placement process.